/**
 * TimesOccur.java created by zhangzhidong 
 * at 下午8:34:36 2016年10月9日
 */
package algorithm;
public class TimesOccur {
	 public int GetNumberOfK(int [] array , int k) {
	       if(array==null || array.length==0)return 0;
	        if(array.length==1){
	            if(array[0]==k) return 1;
	            else return 0;
	        }
	       return get(array,k);
	    }
	    public int get(int arr[],int k){
	        int left = 0;
	        int right = arr.length-1;
	        while(left<=right){
	        	int mid = (left+right)/2;
	            if(arr[mid]==k){
	                int lb = k;
	                int rb = k;
	                while(lb>=0 && arr[lb]==k ){
	                	lb--;
	                }
	                while(rb<=arr.length-1 && arr[rb]==k){
	                    rb++;
	                }
	                return rb-lb-1;
	            }else if(arr[mid]>k){
	              	right = mid-1; 
	            }else{
					left = mid+1;             	   
	            }
	        }
	        return 0;
	    }
	public static void main(String[] args) {
		System.out.println(new TimesOccur().GetNumberOfK(new int[]{3}, 3));
	}

}
